package org.basis.algorithm.practice;

import org.basis.algorithm.common.SortUtil;

import java.util.Arrays;

/**
 * 排序练习
 *
 * @author Mr_wenpan@163.com 2022/03/21 12:43
 */
public class SortPractice {

    public static void main(String[] args) {
//        bubbleSortTest();
//        selectionSortTest();
//        insertionSortTest();
//        mergeSortTest();
        quickSortTest();
    }

    public static void bubbleSortTest() {
        for (int i = 0; i < 10000; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copy = SortUtil.copyArray(arr);
            Arrays.sort(copy);
            bubbleSort(arr);
            if (!SortUtil.isEqual(copy, arr)) {
                System.out.println("bubbleSort fuck!");
            }
        }
    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void selectionSortTest() {
        for (int i = 0; i < 10000; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            selectionSort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("selectionSort fuck!");
                break;
            }
        }
    }

    /**
     * 选择排序
     */
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 每一轮从剩余的元素中选择一个最小的
        for (int i = 0; i < arr.length; i++) {
            // 先认为i位置就是最小的
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                min = arr[min] > arr[j] ? j : min;
            }
            // 交换
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

    public static void insertionSortTest() {
        for (int i = 0; i < 10000; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            insertionSort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("insertionSort fuck!");
                break;
            }
        }
    }

    /**
     * 插入排序
     */
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                // 交换
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
    }

    public static void mergeSortTest() {
        for (int i = 0; i < 10000; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            mergeSort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("mergeSort fuck!");
                break;
            }
        }
    }

    /**
     * 归并排序 1 2 3 4 5 6
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        doMergeSort(arr, 0, arr.length - 1);

    }

    public static void doMergeSort(int[] arr, int l, int r) {
        // base case
        if (l >= r) {
            return;
        }
        int m = (r + l) / 2;
        // 左区间
        doMergeSort(arr, l, m);
        // 右区间
        doMergeSort(arr, m + 1, r);
        // 归并整合左右区间
        doMerge(arr, l, r, m);
    }

    /**
     * 归并
     */
    public static void doMerge(int[] arr, int l, int r, int m) {
        // 辅助数组
        int[] help = new int[r - l + 1];
        int p1 = l;
        int p2 = m + 1;
        int index = 0;

        // 两者都不越界的情况下，谁小拷贝谁
        while (p1 <= m && p2 <= r) {
            if (arr[p1] <= arr[p2]) {
                help[index++] = arr[p1++];
            } else {
                help[index++] = arr[p2++];
            }
        }

        // 只要有任意一个下标越界了，那么就把另一半数组元素全部拷贝到help中
        while (p1 <= m) {
            help[index++] = arr[p1++];
        }

        while (p2 <= r) {
            help[index++] = arr[p2++];
        }

        // 最后将help数组里的元素拷贝回原数组
        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }

    public static void quickSortTest() {
        for (int i = 0; i < 10000; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            quickSort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("quickSort fuck!");
                break;
            }
        }
    }

    /**
     * 快排
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        doQuickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快排问题其实就是荷兰国旗问题的衍生
     */
    public static void doQuickSort(int[] arr, int l, int r) {
        // base case
        if (l >= r) {
            return;
        }
        // 分区
        int[] partition = partition(arr, l, r);
        // 左区间弄成左边小右边大
        doQuickSort(arr, l, partition[0]);
        // 右区间弄成左边小右边大
        doQuickSort(arr, partition[1], r);
    }

    /**
     * 分区，其实就是荷兰国旗问题
     */
    public static int[] partition(int[] arr, int l, int r) {
        int left = l;
        int right = r;
        int index = l;
        while (index < right) {
            if (arr[index] > arr[r]) {
                // 注意：这里index并不往右走一个单位，只将right往左移一个单位
                swap(arr, index, --right);
            } else if (arr[index] < arr[r]) {
                // 左边界右移一个，index向前走一步
                swap(arr, index, left++);
                index++;
            } else {
                // 如果相等，则index继续向右走一步
                index++;
            }
        }

        // 将最后一个位置的元素和right处进行交换
        swap(arr, index, r);

        return new int[]{left - 1, right + 1};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] arr) {

    }

}
